package Algorithm.array;

/**
 * @Desc:   岛屿的最大面积
 * 给定一个包含了一些 0 和 1 的非空二维数组 grid 。
 *
 * 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
 * 你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 *
 * 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
 *
 * 示例
 * [[0,0,1,0,0,0,0,1,0,0,0,0,0],
 *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
 *  [0,1,1,0,1,0,0,0,0,0,0,0,0],
 *  [0,1,0,0,1,1,0,0,1,0,1,0,0],
 *  [0,1,0,0,1,1,0,0,1,1,1,0,0],
 *  [0,0,0,0,0,0,0,0,0,0,1,0,0],
 *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
 *  [0,0,0,0,0,0,0,1,1,0,0,0,0]]
 *
 *  对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1
 *
 *  示例 2:
 *
 * [[0,0,0,0,0,0,0,0]]
 * 对于上面这个给定的矩阵, 返回 0
 *
 * @author: cww
 * @DateTime: 2020-04-05 10:39
 */

public class MaxAreaOfIsland {

    public int maxAreaOfIsland(int[][] grid){
        int sum = 0;
        for (int i=0;i<grid.length;i++){
            for (int j = 0; j < grid.length; j++) {
                sum = Math.max(sum,dfs(i,j,grid));
            }
        }
        return sum;
    }

    public int dfs(int i,int j, int[][] grid){
        if (i<0||j<0||i>=grid.length||j>=grid[i].length||grid[i][j]==0){
            return 0;
        }
        int res = 1;
        grid[i][j] =0;
        res += dfs(i+1,j,grid);
        res += dfs(i-1,j,grid);
        res += dfs(i,j+1,grid);
        res += dfs(i,j-1,grid);
        return res;
    }

}
